public class MergeKLists {
    // lletcode 合并K个升序链表
    // https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSort(lists, 0, lists.length-1);
    }

    private ListNode mergeSort(ListNode[] lists, int left, int right) {
        if (lists == null || lists.length == 0) return null;
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = mergeSort(lists, left, mid);
        ListNode l2 = mergeSort(lists, mid + 1, right);
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null) cur.next = l1;
        if (l2 != null) cur.next = l2;
        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode A = new ListNode(1);
        ListNode B = new ListNode(4);
        ListNode C = new ListNode(5);
        ListNode D = new ListNode(1);
        ListNode E = new ListNode(3);
        ListNode F = new ListNode(4);
        ListNode G = new ListNode(2);
        ListNode H = new ListNode(6);
        A.next = B;
        B.next = C;
        D.next = E;
        E.next = F;
        G.next = H;
        MergeKLists merge = new MergeKLists();
        ListNode[] listNodes = new ListNode[]{A,D,G};
        System.out.println(merge.mergeKLists(listNodes));
    }
}
